A computing system may use a cache memory to improve computing performance. For instance, a computing system may store data that it needs to access more frequently in a smaller, faster cache memory instead of storing the data in a slower, larger memory (e.g., a main memory unit). Accordingly, the computing system is able to access the data quicker, which can reduce the latency of memory accesses.
Real time and general time sharing operating systems typically use nested preemption in scheduling tasks and interrupts. For example, fixed priority systems will preempt a currently running process when a higher priority process becomes ready to run. When this happens, the information about the currently running process is saved and it is not used until the higher priority process has finished running. For example, consider that Task X is preempted by Task Y and Task Y is then preempted by Task Z. Task Z will finish running first and Task Y will resume. Once Task Y finishes running, Task X will resume. The benefit of preemption is that the higher priority Task Z is allowed to run sooner and handle its more urgent work before its deadline.
However preemption has costs. The first cost is the overhead required to save the information of Task X and switch to Task Y. Then the cost is incurred again to save the information of Task Y and switch to Task Z. Operating systems and hardware have been designed to minimize this cost. The second cost is termed Cache Related Preemption Delay (CRPD). When higher priority tasks run, if space is not available in cache memory, they will evict cache entries from current tasks. This will cause the current task to miss the cache when it resumes execution and have to wait for data from the more distant main memory.
This cost is worsened by the typical Least Recently Used (LRU) caching strategies. Under LRU, data associated with older tasks are evicted before data associated with more recent tasks. Thus, in the above example, when Task X brings back in data it needs, the remaining cache entries for preempted Task X will be evicted first to make room for the new data, and the entries for higher priority Task Y and Task Z will be preserved even though they have completed execution. Studies have shown that the impact of CRPD can be as high as 44%.